package sort;

// 以下排序都是：从小到大

import java.util.Stack;

public class Sort {
    /** 直接插入排序：
     * 时间复杂度：等比数列求和
     *   最坏：O(N^2) 逆序
     *   最好：O(N) 有序
     *   结论：对于直接插入排序来说，数据越有序越快。
     *   场景：当数据基本有序的时候就使用直接插入排序。
     * 空间复杂度：O(1)
     * 稳定性：tmp<arr[j]时不加=就是稳定，加了就不稳定了
     *   一个本身就稳定的排序，你可以实现为不稳定；
     *    但是一个本身就不稳定的排序，是没有办法变成稳定的排序的。
     * @param arr
     */
    public void insertSort(int[] arr) {
        // 从第二个元素开始排序
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            // 进行比较
            int j = i-1;
            for (; j >= 0; j--) {
                if(tmp<arr[j]) {
                    // 小于就j往前挪,然后j的值往后移动
                    arr[j+1] = arr[j];
                    // 注意这里不需要再次j--，条件已经在括号中
                } else {
                    // 大于则直接插入
                    // arr[j+1] = tmp; // 也可以拿到循环外面，这样的话j要定义在外面！
                    // 结束循环
                    break;
                }
            }
            // 大于则直接插入
            arr[j+1] = tmp;
        }
    }


    /**
     * 希尔排序：
     * 设组数（增量值）gap，则首元素j=i-gap,第二个元素i=gap,之后进行i++，j也会随着变化
     * 时间复杂度： O(N^1.3)~ O(N^1.5)
     * 空间复杂度： O(1)
     * 稳定性： 不稳定
     */
    private static void shell(int[] arr, int gap) {
        // i表示后面的元素
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            // 进行比较
            int j = i-gap;
            for (; j >= 0; j-=gap) { // 注意此时j的变换条件是j-=gap，因为交换的是对应的两个元素！
                if(tmp<arr[j]) {
                    // 小于就j往前挪,然后j的值往后移动
                    arr[j+gap] = arr[j];

                } else {
                    // 大于则直接插入
                    // arr[j+gap] = tmp; // 也可以拿到循环外面，这样的话j要定义在外面！
                    // 结束循环
                    break;
                }
            }
            // 大于则直接插入
            arr[j+gap] = tmp;
        }
    }

    public static void shellSort(int[] arr) {
        // 问题：如何确定增量值？
        /*int[] drr = {5,2,1};
        for (int i = 0; i < drr.length; i++) {
            shell(arr,drr[i]);
        }*/

        int gap = arr.length;
        while(gap > 1) {
            shell(arr,gap);
            gap  /= 2;  // 注意变换！！
        }
        // 最后进行一次增量值为1的排序就行
        shell(arr,1);
    }



    /**
     * 直接选择排序：
     * 时间复杂度：等差数列求和(N-1+N-2+...+1+0)，即：O(N^2)-->对数据不敏感，不管是有序还是无序，时间复杂度都是一样的
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void selectSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len-1; i++) { // 最后一个数据不用比较
            int minIndex = i; // 记录当前被比较的下标,以此作为最小值的对照条件
            for (int j = i+1; j < len; j++) {
                if(arr[minIndex] > arr[j]) {
                    // 进行minIndex的更新
                    minIndex = j;
                }
            }
            // 来到这儿说明找到minIndex最终值,是要把minIndex值与i值进行交换，而不是简单的赋值
            // 简单的赋值会丢失原来i下标所指的值
            // arr[i]= arr[minIndex];
            swap(arr,minIndex,i);
        }
    }
    // 交换方法
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 直接选择排序的优化：一次选择两个元素--> 一个最小minIndex放最左边left，一个最大maxIndex放最右边right
     * 完成一次后left++ right-- 但是要始终保证该循环是在left<right条件下进行的
     * minIndex/maxIndex首先都标记为left
     * 时间复杂度依旧是：O(N^2)
     */
    public static void selectSort2(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        //for (int i = 0; i <= arr.length/2; i++) {
        while(left<right) {
            int minIndex = left;
            int maxIndex = left; // 首先进行标记,都以未排序的最左边为min、max

            for (int i = left+1; i <= right; i++) { // 注意i从left+1开始
                if(arr[i]<arr[minIndex]) { // 更小就更新
                    minIndex = i;
                }
                if(arr[i]>arr[maxIndex]) { // 更大就更新
                    maxIndex = i;
                }
            }
            // 标记好后进行交换
            // 直接min交换完交换max可能会存在一个问题：如果left==max，而又有min需要left与min交换，
            // 交换后原来的max就变了，之后的right与max交换就不是原来的值，就会出错。
            swap(arr,left,minIndex);
            // 交换完后进行判断，修正 max的下标！！！
            if(left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(arr,right,maxIndex);

            // 完成交换后进行left right变换
            left++;
            right--;
        }
    }




    /**
     * 堆排序：建堆（【调整】）
     *
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void heapSort(int[] arr) {
        // 创建大根堆：（从小到大）
        createBigHeap(arr);
        // 最后一个元素与堆顶元素进行交换
        int end = arr.length-1;
        while(end>=0) {
            swap(arr,0,end);
            // 进行【向下调整】：注意源码中是<len
            shiftDown(arr,0,end);
            end--; // 调整好后最后一个数据就是maxValue，将其排除后进行循环比较
        }
    }
    // 建大根堆
    private static void createBigHeap(int[] arr) {
        // 先确定最后一颗子树的根结点，根据根结点进行建堆
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            // 由根结点开始【向下调整】
            shiftDown(arr,parent,arr.length);
        }
    }
    // 向下调整
    private static void shiftDown(int[] arr,int parent, int len) { // 结束位置是数组长度！
        // 左右孩子比较取最大，然后最大孩子结点与根结点进行比较，是否交换
        int child = 2*parent+1;
        // 最起码保证左孩子存在
        while(child<len) {
            if(child+1<len && arr[child]<arr[child+1]) {
                child++; // child存储最大值下标
            }
            if(arr[child] > arr[parent]) {
                swap(arr,child,parent);
                // 交换完之后进行parent与child的调整，保证在交换后其子树也是满足大根堆
                parent = child;
                child = 2*parent+1;
            } else {
                break; // 满足大根堆就直接终止循环
            }
        }
    }





    /**
     * 冒泡排序：
     * 趟数（n个数据搞n-1趟） 以及 每趟比较的对数（n-1-i）：因为每经历一趟就可以减少1对数据比较
     * 趟数+对数=总数据个数-1
     * 时间复杂度：O(N^2)--等差数列求和
     * 针对优化后的代码（也就是增加了flag标记）：在有效情况下时间复杂度是O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定的。（在比较时如果加了=就是不稳定的）
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {  // 趟数
            boolean flag = false;
            for (int j = 0; j < arr.length-1-i; j++) { // 每趟比较的对数
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                    // 如果检测到该对数据经过了交换，那就说明：该组数据还不是有序数据。
                    flag = true;
                }
            }
            // 来到这儿，说明一趟遍历完成，此时如果经过交换就说明不是有效的，继续；
            // 如果是false就说明不交换已经是有序的，直接over
            if (!flag) {
                break;
            }
        }
    }





    /**
     * 快速排序
     * Hoare版：左key，右先动；直到相遇交换key。
     * 时间复杂度：理想情况下（每次都是均分）的时间复杂度是：O(N*logN) 每一层是N次，一共有logN层（相当于树的高度）
     * 时间复杂度：最慢（即：有序or逆序情况下）是：O(N^2)--等差数列求和
     * 空间复杂度： 最好（均分）：O(logN)  最坏（单分支）：O(N)--当N足够大时深度就足够大，栈溢出风险就越大
     * 稳定性：不稳定
     * 当有序数组中数据个数过大时进行快排可能hi出现栈溢出的情况！
     * 为什么会出现栈溢出：因为递归的深度太深了，而函数的递归是在栈上开辟栈帧的
     * 一般情况下，快排的使用场景是：无序场景。
     * 如果发现数据趋于有序，就使用直接插入排序or希尔排序！
     * 但是快排在有序的情况下栈溢出确实是目前存在的问题，我们需要就这个问题进行处理。
     *
     */
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    // 快排方法
    private static void quick(int[] arr, int left, int right) {
        // 在求基准值过程中，如果数组直接是有序的，就会出现，left==right==pivot
        // 此时说明基准值只有一个结点or没有结点
        if(left >= right) {
            return;
        }
        // 找到基准值
        int pivot = partition(arr,left,right);
        // 继续递归
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    // 找基准值
    private static int partition(int[] arr, int start, int end) {
        // 实现存储好key下标
        int i = start;
        int key = arr[start];
        while(start<end) {
            // 为什么前面还要加上start<end？ 因为这是一个独立循环，又可能会出现key之后的all值都小于key值，
            // 此时end一直会减小到end==-1，也就是错过了相遇点
            // 为什么 arr[end]>=key、arr[start]<=key需要取等号？ 因为不取等号可能会陷入死循环
            while(start<end && arr[end]>=key) {
                end--;
            }
            // 出来说明：①end==start ②arr[end]<key，需要找start
            while(start<end && arr[start]<=key) {
                start++;
            }
            // 此时进行交换
            swap(arr,start,end);
        }
        // 完成交换后，start与end相遇，此时要与key下标进行交换
        swap(arr,start,i);
        //return i; // 新的基准下标，注意不是i，是start，因为交换的只是下标对应的值！！
        return start; // 相遇处被交换到了新的基准值（新的基准下标）
    }



    /**
     * 快速排序优先考虑使用挖坑法！！
     * 快速排序：
     * 挖坑法:其实也就是相较于Hoare法在寻找基准值时会有变化而已，
     * 这个相当于start与end交换，最后在相遇处的坑位填上key，也就是寻找的基准值
     *
     */
    public static void quickSort2(int[] arr) {
        quick2(arr,0,arr.length-1);
    }
    // 快排方法
    private static void quick2(int[] arr, int left, int right) {
        // 在求基准值过程中，如果数组直接是有序的，就会出现，left==right==pivot
        // 此时说明基准值只有一个结点or没有结点
        if(left >= right) {
            return;
        }
        // 找到基准值
        int pivot = partitionHole(arr,left,right);
        // 继续递归
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    // 找基准值
    private static int partitionHole(int[] arr, int start, int end) {
        int key = arr[start]; // 进行key的标记
        while(start<end) {
            // 为什么前面还要加上start<end？ 因为这是一个独立循环，又可能会出现key之后的all值都小于key值，
            // 此时end一直会减小到end==-1，也就是错过了相遇点
            // 为什么 arr[end]>=key、arr[start]<=key需要取等号？ 因为不取等号可能会陷入死循环
            while(start<end && arr[end]>=key) {
                end--;
            }
            // 出来说明：①end==start ②arr[end]<key
            arr[start] = arr[end];
            while(start<end && arr[start]<=key) {
                start++;
            }
            arr[end] =arr[start];
        }
        // 完成交换后，start与end相遇，此时key值应该放入该坑位
        arr[start] = key;
        return start; // 相遇处被交换到了新的基准值（新的基准下标）
    }


    /**
     * 快速排序：
     * 前后指针法：比基准小就一直走，且不重叠就进行交换
     */
    public static void quickSort3(int[] arr) {
        quick3(arr,0,arr.length-1);
    }
    // 快排方法
    private static void quick3(int[] arr, int left, int right) {
        // 在求基准值过程中，如果数组直接是有序的，就会出现，left==right==pivot
        // 此时说明基准值只有一个结点or没有结点
        if(left >= right) {
            return;
        }
        // 找到基准值
        int pivot = partitionPointer(arr,left,right);
        // 继续递归
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    // 找基准值
    private static int partitionPointer(int[] arr, int start, int end) {
        // 注意：start是就是基准位！！！
       int prev = start;
       int cur = start+1;
       while(cur <= end) {
           if(arr[cur]<arr[start] && arr[++prev]!=arr[cur]) {
               // 当前值小于基准值且pre下一个与cur值不重叠就进行交换
               // 此时prev里存的是大于基准值的，cur是小于基准值的，两个进行交换
               swap(arr,prev,cur);
           }
           // 说明：①cur值大于基准值 or ②重叠 or 上述进行了交换（cur>, prev<）
           cur++;
       }
       // 说明 cur已经走完了
        swap(arr,prev,start);
       return prev;
    }


    /**
     * 优化快速排序算法：
     *
     * （单分支：其实就是有序的数据（顺序or逆序））：此时容易造成栈溢出
     * 解决方案：1.随机选取基准法（随机选取基准与首元素进行交换作为新的基准）--然后就是相同方法--递归
     *   2.三数取中法（start/end/middle的中位数换到start位置作为新的基准值）
     */

    /**
     * 下面实现三数取中法：
     */
    // 三个数找中位数下标：
    private static int midNumIndex(int[] arr,int left,int right) {
        int middle = (left+right)/2;
        if(arr[left] < arr[right]) {
            if(arr[middle] < arr[left]) {
                return left;
            } else if(arr[middle] > arr[right]) {
                return right;
            } else {
                return middle;
            }
        } else {
            if(arr[middle] > arr[left]) {
                return left;
            } else if(arr[middle] < arr[right]) {
                return right;
            } else {
                return middle;
            }
        }
    }
    public static void quickModify(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        // 找中位数下标并及交换
        int index = midNumIndex(arr,left,right);
        swap(arr,index,left);
        // 进行基准值位置更换确定
        int pivot = partition(arr,left,right);
        // 递归
        quickModify(arr,left,pivot-1);
        quickModify(arr,pivot+1,right);
    }


    /**
     * 快排优化2：
     * 递归到小区间且数据已经趋于有序时，就使用【直接插入排序：指定区间】
     *
     * 注意：说道快排的时间复杂度一般是：O(N*logN)，一般不说最慢O(N^2)，因为如果有序数据直接使用直插
     */
    // 指定区间的直接插入排序：
    private static void insertSort2(int[] arr,int start, int end) {
        // 从第二个元素开始排序
        for (int i = start+1; i <= end; i++) { // end处取整，因为参数给的是right
            int tmp = arr[i];
            // 进行比较
            int j = i-1;
            for (; j >= start; j--) {
                if(tmp<arr[j]) {
                    // 小于就j往前挪,然后j的值往后移动
                    arr[j+1] = arr[j];
                    // 注意这里不需要再次j--，条件已经在括号中
                } else {
                    // 大于则直接插入
                    // arr[j+1] = tmp; // 也可以拿到循环外面，这样的话j要定义在外面！
                    // 结束循环
                    break;
                }
            }
            // 大于则直接插入
            arr[j+1] = tmp;
        }
    }
    public static void quickModify2(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 判断小区间 + 【直接插入排序】:注意小区间的选取！！
        // 主要优化了递归深度
        if (right - left + 1 <= 7) {
            insertSort2(arr, left, right);
            return;
        }
        // 找中位数下标并及交换
        // 三数取中：解决递归深度问题，有了三数取中后待排序序列基本上都是二分N*logN
        int index = midNumIndex(arr, left, right);
        swap(arr, index, left);
        // 进行基准值位置更换确定
        int pivot = partition(arr, left, right);
        // 递归
        quickModify2(arr, left, pivot - 1);
        quickModify2(arr,pivot+1,right);
    }


    /**
     * 注意：到目前，只有直接插入排序 和 冒泡排序 是稳定的，其余都是不稳定的！
     *
     * 非递归的快排：
     * 使用栈
     */
    public static void quickSortNo(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        int pivot = partitionHole(arr,left,right);
        // 下标入栈:只有当基准值左右有大于1个元素时才入展，只有一个元素是不入栈的！！
        // 首先必须有一次的入栈！！
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(right > pivot+1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        // 如果栈不为空就弹出两个元素，弹出的元素作为新的left和right!!!,继续进行partition找基准值，之后又进行入栈，直到栈为空
        // 其实这个循环就是一边一边的进行寻找基准值以及排序
        while(!stack.isEmpty()) {
            // 出栈
            right = stack.pop();
            left = stack.pop();
            // 找基准+排序
            // 这里进行基准值下标的更新，否则会陷入死循环
            pivot = partition(arr,left,right);
            // 入栈
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(right > pivot+1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }


    }

    /**
     * 非递归的快排：再优化：三数取中（使用partition都可以使用）
     */
    public static void quickSortNo2(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        // 三数取中：作为left
        int index = midNumIndex(arr, left, right);
        swap(arr, index, left);
        // 寻找基准值
        int pivot = partitionHole(arr,left,right);
        // 下标入栈:只有当基准值左右有大于1个元素时才入展，只有一个元素是不入栈的！！
        // 首先必须有一次的入栈！！
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(right > pivot+1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        // 如果栈不为空就弹出两个元素，弹出的元素作为新的left和right!!!,继续进行partition找基准值，之后又进行入栈，直到栈为空
        // 其实这个循环就是一边一边的进行寻找基准值以及排序
        while(!stack.isEmpty()) {
            // 出栈
            right = stack.pop();
            left = stack.pop();
            // 三数取中+找基准+排序
            // 这里进行基准值下标的更新，否则会陷入死循环
            index = midNumIndex(arr, left, right);
            swap(arr, index, left);
            pivot = partition(arr,left,right);
            // 入栈
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(right > pivot+1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }


    }




    /**
     * 归并排序：
     * 先分解 再整合
     *
     * 不管有序无序，时间复杂度是：O(N*logN)
     * 空间复杂度：O(N):归并到新的数组
     * 稳定性：有等号就稳定
     *
     * 三个稳定的排序：直插、冒泡、归并
     */
    private static void mergeFunc(int[] arr,int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left+right)/2;
        // 分解左边
        mergeFunc(arr,left,mid); // 是包含mid
        // 分解右边
        mergeFunc(arr,mid+1,right);
        // 进行合并
        merge(arr,left,right,mid);
    }
    // 合并
    private static void merge(int[] arr, int left, int right, int mid) {
        // 首先申请一个数组，大小是两边的元素个数之和
        int[] tmpArr = new int[right-left+1];
        // 定义数组下标
        int k =0;
        // 循环决定两个序列的顺序，注意循环条件是：两个序列都要有元素
        // 只要一个为空就停止循环，另一个序列直接跟上
        // 即：只有两个归并段都有数据时才进入循环比较大小
        // 创建临时变量！
        int s2 = mid+1;
        int start = left;
        while(left<=mid && s2<=right) {
            if(arr[left] <= arr[s2]) { // 有无等号决定了稳定性：有稳定
               /* tmpArr[k] = arr[left];
                // 进入数组（小的那个段进行++移向下一个数据）
                left++;
                k++; // 临时数组存入数据后下标也要进行移动*/

                // 其实以上就是left与k先使用再加加，即后置加加
                tmpArr[k++] = arr[left++];
            } else {
                /*tmpArr[k] = arr[s2];
                s2++;
                k++;*/
                tmpArr[k++] = arr[s2++];
            }
        }
        // 判断是哪个序列需要再进行拷贝（循环），此时一个归并段没有了元素
        while (left<=mid) {
            tmpArr[k++] = arr[left++];
        }
        while (s2<=right) {
            tmpArr[k++] = arr[s2++];
        }
        // 把排好序的数据拷贝会原来数组
        // 注意拷贝回原数组时不是按0开始的，而是原来数组开始进行合并的初始与结束位，即：每次合并时位置都不一样
        for (int i = 0; i < k; i++) {
            arr[i+start] = tmpArr[i]; // 注意原数组的位置要+start！！！
        }
    }
    public static void mergeSort(int[] arr) {
        mergeFunc(arr,0,arr.length-1);
    }


    /**
     * 非递归实现归并排序：
     * 控制每一组数据的个数
     */
    public static void mergeSortNo(int[] arr) {
        int gap = 1; // 每组的数据
        while(gap < arr.length) {
            // 每次进来（不管一组有多少个元素）都是要把all元素遍历完
            for (int i = 0; i < arr.length; i+= (gap*2)) { // 注意变换条件！！
                // 进入该循环说明i是合法的
                int s1 = i;
                int e1 = s1+gap-1;
                // e1可能会越界，要进行修正！
                if(e1>=arr.length) {
                    e1 = arr.length-1;
                }
                // 其实因为该过程中s2都是起辅助作用的，没有实际用到，所以可以不写出来
                /*int s2 = e1+1;
                if(s2>=arr.length) {
                    s2 = arr.length-1;
                }
                int e2 = s2+gap-1;*/
                int e2 = e1+gap;
                if(e2>=arr.length) {
                    e2 = arr.length-1;
                }
                merge(arr,s1,e2,e1);
            }
            gap *= 2;
        }
    }

    // 数据量较大时：快排、归并、希尔、堆




    /**
     * 计数排序：需要一个计数器（确定稿计数器数组的个数：max-min+1）
     * 计数排序：适合给定一个范围的数据排序
     * 时间复杂度：O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：稳定（但是其实不太确定—）
     */
    public static void countSort(int[] arr) {
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < minValue) {
                minValue = arr[i];
            }
            if(arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }
        // 来到这儿：已经找到最大最小值
        int len = maxValue-minValue+1; // 计数器数组长度
        int[] count = new int[len];
        // 注意值对应的计数器位置
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            count[val-minValue]++; //所存的值就是【下标+minValue】
        }
        // 排好序后写回到原来的arr数组
        // 定义arr数组下标
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            // 注意是：while循环而不是if，因为可能在有重复值！！
            while(count[i]!=0) {
                arr[index] = i+minValue; // 注意不要忘记加minValue！！
                index++;
            }
        }
    }


    /**
     * 基数排序：
     */
}
